#include<iostream>
#include<algorithm>
using namespace std;

template<class K>
class BSTreeNode{              //二叉搜索树的节点类封装
public:

    BSTreeNode(const K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
    {}

    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
};

template<class K>
class BSTree{                               //二叉树搜索树类的封装
    typedef BSTreeNode<K> Node;
public:
    BSTree()                                //构造函数
    :_root(nullptr)
    {
        cout<<"BSTree()"<<endl;
    }

    ~BSTree(){                              //析构函数
        cout<<"~BSTree()"<<endl;
        Destroy(_root);
    }

    BSTree(const BSTree<K>& t){             //拷贝构造函数
        cout<<"BSTree(const BSTree<K>& t)"<<endl;
        _root=Copy(t._root);
    }

    BSTree<K>& operator=(BSTree<K>& t){     //赋值运算符重载
        swap(_root,t._root);
        return *this;
    }

    void InOrder(){                         //中序遍历
        _InOrder(_root);
        cout<<endl;
    }
 
    bool FindR(const K& key){               //递归查找函数
        return _FindR(_root,key);
    }

    bool InsertR(const K& key){             //递归插入函数
        return _InsertR(_root,key);
    }

    bool EraseR(const K& key){              //递归删除函数
        return _EraseR(_root,key);
    }

    bool Find(const K& key){
        if(_root==nullptr){
            return false;
        }
        Node* cur=_root;
        while(cur){
            if(cur->_key<key){
                cur=cur->_right;
            }
            else if(cur->_key>key){
                cur=cur->_left;
            }
            else{
                return true;
            }
        }
        return false;
    }

    bool Insert(const K& key){              //插入节点函数
        if(_root==nullptr){                 //如果当前是空树，直接创建根节点
            _root=new Node(key);
            return true;
        }
        else{
            Node* cur=_root;
            Node* parent=cur;
            while(cur){
                if(cur->_key<key){
                    parent=cur;
                    cur=cur->_right;
                }
                else if(cur->_key>key){
                    parent=cur;
                    cur=cur->_left;
                }
                else{
                    return false;
                }
            }
            cur=new Node(key);
            if(parent->_key<key){
                parent->_right=cur;
            }
            else{
                parent->_left=cur;
            }
        }
        return true;
    }

    bool Erase(const K& key){
        Node* parent=nullptr;
        Node* cur=_root;

        while(cur){
            if(cur->_key<key){
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_key>key){
                parent=cur;
                cur=cur->_left;
            }
            else{                                                 //找到删除节点
                if(cur->_left==nullptr){                          //删除的左子结点为空
                    if(cur==_root){                               //且是根节点的情况
                        _root=cur->_right;
                    }
                    else{                                         //不是根节点的情况
                        if(parent->_right==cur){                  //父节点的右子节点是删除节点
                            parent->_right=cur->_right;
                        }
                        else{                                     //父节点的左子结点是删除节点
                            parent->_left=cur->_right;
                        }
                    }
                }
                else if(cur->_right==nullptr){                    //删除的右子节点为空
                    if(cur==_root){                                //且是根节点
                        _root=cur->_left;
                    }
                    else{                                         //不是根节点的情况
                        if(parent->_right==cur){                  //父节点的右子节点是删除节点
                            parent->_right=cur->_left;
                        }
                        else{                                     //父节点的左子结点是删除节点
                            parent->_left=cur->_left;
                        }
                    }
                }
                else{                                             //删除的节点左右子节点都不为空
                    Node* parent=cur;                             //父节点初始时必须指向cur节点
                    Node* leftMax=cur->_left;                     //定义一个leftMax节点用来找左子树的最大节点也是最右节点
                    while(leftMax->_right){
                        parent=leftMax;
                        leftMax=leftMax->_right;
                    }

                    swap(cur->_key,leftMax->_key);              //交换需要删除的节点和找到的替换节点的值
                    if(parent->_left==leftMax){                   
                        parent->_left=leftMax->_left;
                    }
                    else{
                        parent->_right=leftMax->_right;
                    }
                    cur=leftMax;

                }
            delete cur;                                           //释放需要删除的节点
            cur=nullptr;                                          //节点置为空
            return true;
            }
        }
        return false;
    }

private:
    void _InOrder(Node* root){                                   //中序遍历子函数
        if(root==nullptr){
            return;
        }
        _InOrder(root->_left);
        cout<<root->_key<<" ";
        _InOrder(root->_right);
    }

    void Destroy(Node* root){                                    //析构函数子函数
        if(root==nullptr){                                       //后序遍历即可
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
        root=nullptr;
    }

    Node* Copy(Node* root){                                     //拷贝构造子函数
        if(root==nullptr){                                      //前序遍历即可
            return nullptr;
        }
        Node* copyroot=new Node(root->_key);
        copyroot->_left=Copy(root->_left);
        copyroot->_right=Copy(root->_right);
        return copyroot;

    }

    bool _FindR(Node*& root,const K& key){                      //递归查找子函数
        if(root==nullptr){
            return false;
        }
        if(root->_key<key){
            return _FindR(root->_right,key);
        }
        else if(root->_key>key){
            return _FindR(root->_left,key);
        }
        else{
            return true;
        }
    }

    bool _InsertR(Node*& root,const K& key){                      //递归插入子函数
        if(root==nullptr){                                        //如果当前节点为空，说明找到了插入的位置
            root=new Node(key);                                   //因为指针引用，所以直接创造新节点
            return true;                                          //插入成功，返回true
        }

        if(root->_key<key){                                       //当前节点_key值小于key值，到右子树中查找
            return _InsertR(root->_right,key);
        }
        else if(root->_key>key){                                  //当前节点_key值大于key值，到左子树中查找
            return _InsertR(root->_left,key);
        }
        else{                                                     //当前节点_key值等于key值，说明已经存在，返回false
            return false;
        }
    }

    bool _EraseR(Node*& root,const K& key){                      //递归删除子函数
        if(root==nullptr){                                       //如果当前节点为空，说明没有找到要删除的节点
            return false;                                        //返回false
        }
        if(root->_key<key){                                      //当前节点_key值小于key值，到右子树中查找
            return _EraseR(root->_right,key);
        }
        else if(root->_key>key){                                 //当前节点_key值大于key值，到左子树中查找
            return _EraseR(root->_left,key);
        }
        else{                                                    //当前节点_key值等于key值，说明找到要删除的节点
            Node* del=root;                                      //从新顶一个指针指向当前要删除的节点                  
            if(root->_left==nullptr){                            //删除节点左子结点为空                   
                root=root->_right;                               //root指向删除节点的右子节点
            }
            else if(root->_right==nullptr){                      //删除节点右子结点为空 
                root=root->_left;                                //root指向删除节点的左子节点
            }
            else{                                                //如果删除节点的左右子节点都不为空
                Node* leftMax=root->_left;                       //定义一个新的节点指针指向删除节点的左子结点
                while(leftMax->_right){                          //查找替换节点，左子树的最大节点，也是最右节点
                    leftMax=leftMax->_right;
                }
                swap(root->_key,leftMax->_key);                  //交换删除节点和替换节点的值
                return _EraseR(root->_left,key);                  //再从左子树中查找要删除的节点
            }
            delete del;                                          //释放删除节点
            del=nullptr;                                         //节点置为空
        }
        return true;
    }


private:
    Node* _root;
};